package shiyan3;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Objects;

public class SparseMatrix {
    private final int numRows;
    private final int numCols;
    private final List<Entry> entries;

    public SparseMatrix(int numRows, int numCols) {
        if (numRows <= 0 || numCols <= 0) {
            throw new IllegalArgumentException("Matrix dimensions must be positive");
        }
        this.numRows = numRows;
        this.numCols = numCols;
        this.entries = new ArrayList<>();
    }

    public void set(int row1Based, int col1Based, double value) {
        validateIndices(row1Based, col1Based);
        int r = row1Based - 1;
        int c = col1Based - 1;
        int idx = findEntryIndex(r, c);
        if (value == 0.0) {
            if (idx >= 0) {
                entries.remove(idx);
            }
            return;
        }
        if (idx >= 0) {
            entries.get(idx).value = value;
        } else {
            Entry e = new Entry(r, c, value);
            int insertPos = -idx - 1;
            entries.add(insertPos, e);
        }
    }

    public double get(int row1Based, int col1Based) {
        validateIndices(row1Based, col1Based);
        int r = row1Based - 1;
        int c = col1Based - 1;
        int idx = findEntryIndex(r, c);
        return idx >= 0 ? entries.get(idx).value : 0.0;
    }

    public int getNumRows() {
        return numRows;
    }

    public int getNumCols() {
        return numCols;
    }

    public int getElementCount() {
        return numRows * numCols;
    }

    public int getNonZeroCount() {
        return entries.size();
    }

    public double getSparsityFactor() {
        return 1.0 - ((double) getNonZeroCount() / (double) getElementCount());
    }

    public void printMatrix() {
        System.out.println("矩阵（" + numRows + " x " + numCols + "）：");
        int cursor = 0;
        for (int i = 0; i < numRows; i++) {
            StringBuilder rowBuilder = new StringBuilder();
            for (int j = 0; j < numCols; j++) {
                double v = 0.0;
                while (cursor < entries.size()
                        && (entries.get(cursor).row < i
                                || (entries.get(cursor).row == i && entries.get(cursor).col < j))) {
                    cursor++;
                }
                if (cursor < entries.size()
                        && entries.get(cursor).row == i
                        && entries.get(cursor).col == j) {
                    v = entries.get(cursor).value;
                }
                rowBuilder.append(String.format("%8.2f", v));
            }
            System.out.println(rowBuilder);
        }
    }

    public void printInfo() {
        System.out.println("稀疏矩阵信息：");
        System.out.println("- 矩阵维度： " + numRows + " x " + numCols);
        System.out.println("- 矩阵元素总数： " + getElementCount());
        System.out.println("- 非零元素个数： " + getNonZeroCount());
        System.out.printf("- 稀疏因子δ： %.6f%n", getSparsityFactor());
        System.out.println("- 存储方式：有序三元组（行, 列, 值），按（行, 列）排序");
    }

    public List<int[]> getNonZeroCoordinates() {
        List<int[]> coords = new ArrayList<>(entries.size());
        for (Entry e : entries) {
            coords.add(new int[] { e.row + 1, e.col + 1 });
        }
        return coords;
    }

    private void validateIndices(int row1Based, int col1Based) {
        if (row1Based < 1 || row1Based > numRows || col1Based < 1 || col1Based > numCols) {
            throw new IndexOutOfBoundsException("Indices out of bounds: (" + row1Based + ", " + col1Based + ")");
        }
    }

    private int findEntryIndex(int row0, int col0) {
        int left = 0;
        int right = entries.size() - 1;
        while (left <= right) {
            int mid = (left + right) >>> 1;
            Entry e = entries.get(mid);
            if (e.row == row0 && e.col == col0) {
                return mid;
            }
            if (e.row < row0 || (e.row == row0 && e.col < col0)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -(left) - 1;
    }

    private static final class Entry {
        int row; // 0-based
        int col; // 0-based
        double value;

        Entry(int row, int col, double value) {
            this.row = row;
            this.col = col;
            this.value = value;
        }
    }
}
